package main.Q1301_1400;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Q1371_1380 {
    public static void main(String[] args) {
        System.out.println("Question1371：");
        System.out.println("Question1372：");
        System.out.println("Question1373：");
        System.out.println("Question1374：");
        System.out.println("Question1375：");
        System.out.println("Question1376：通知所有员工所需的时间");
        int[] manager={-1,5,0,6,7,0,0,0},informTime={89,0,0,0,0,523,241,519};
        System.out.println(new Question1376().numOfMinutes(8,0,manager,informTime));
        System.out.println("Question1377：");
        System.out.println("Question1378：");
        System.out.println("Question1379：");
        System.out.println("Question1380：");
    }
}

class Question1376{
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        int arraySize = n;
        List<Integer>[] indexs = new ArrayList[arraySize];
        for (int i = 0; i < arraySize; i++) {
            indexs[i] = new ArrayList<>();
        }
        int root = 0;
        for (int i = 0; i < manager.length; i++) {
            if (manager[i] == -1) {
                root = i;
            } else
                indexs[manager[i]].add(i);
        }
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] { root, 0 });
        int ans = 0;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int f = cur[0], t = cur[1], it = t + informTime[f];
            ans = Math.max(ans, t);
            List<Integer> next = indexs[cur[0]];
            for (int nxt : next) {
                queue.add(new int[] { nxt, it });
            }
        }
        return ans;
    }
}